class Solution {
public:
    unordered_map<char,unordered_set<char>> us;
    unordered_map<char,int> hash;
    string alienOrder(vector<string>& words) {
        for(auto& ch:words)
        {
            for(auto& s:ch)
            {
                hash[s]=0;
            }
        }

        int n=words.size();
        for(int i=0;i<n-1;++i)
        {
                if(!func(words[i],words[i+1]))
                {
                    return "";
                }
        }
        queue<char> q;
        for(auto [x,y]: hash)
        {
            if(y==0)
            {
                q.push(x);
            }
        }
        string tmp;
        while(q.size())
        {
            char t=q.front();
            q.pop();
            tmp+=t;
            for(auto& ch:us[t])
            {
                hash[ch]--;
                if(hash[ch]==0)
                {
                    q.push(ch);
                }
            }
        }
        for(auto& [a,b]:hash)
        {
            if(b!=0) return "";
        }
        return tmp;
    }

    bool func(string& w1,string& w2)
    {
        int n=min(w1.size(),w2.size());
        bool check = false;
        for(int i=0;i<n;++i)
        {
            if(w1[i]!=w2[i])
            {
                char a=w1[i];
                char b=w2[i];//a->b
                if(us[a].insert(b).second)
                {
                    hash[b]++; 
                }  
                check=true;
                break; 
            }
        }
        if(!check&&w1.size() > w2.size())
        {
            return false;
        }
        return true;
    }
};
